public class Test_8_25 {

    //牛客网：CM11 链表分割
    public ListNode partition(ListNode pHead, int x) {
        if(pHead == null) return null;

        ListNode head1 = new ListNode(-1);      //比x值小的链表
        ListNode head2 = new ListNode(-1);      //比x值大的链表
        ListNode lN1 = head1;           //比x值小的链表的链尾
        ListNode lN2 = head2;           //比x值大的链表的链尾

        while(pHead != null) {
            if(pHead.val < x) {
                lN1.next = pHead;
                lN1 = lN1.next;
            }else {
                lN2.next = pHead;
                lN2 = lN2.next;
            }
            pHead = pHead.next;
        }
        //防止链表中最大的值不在链尾
        lN2.next = null;
        lN1.next = head2.next;
        return head1.next;
    }


    //牛客网：OR36 链表的回文结构
    public boolean chkPalindrome(ListNode A) {
        if(A == null) return false;
        if(A.next == null) return true;

        ListNode fast = A;
        ListNode slow = A;
        ListNode preSlow = A;
        //slow定位到链表的中间部分
        while(fast != null && fast.next != null) {
            if(slow != A) {
                preSlow = preSlow.next;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        preSlow.next = null;

        //从slow位置的结点开始，使用头插法反转链表
        ListNode cur = slow.next;
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        while(A != null) {
            if(A.val != slow.val) {
                return false;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }


    //力扣：160. 相交链表
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //1.确定链表A和B各自的长度
        ListNode pL = headA;
        ListNode pS = headB;
        int lengthA = 0;
        int lengthB = 0;
        while(pL != null) {
            lengthA++;
            pL = pL.next;
        }
        while(pS != null) {
            lengthB++;
            pS = pS.next;
        }

        //2.让较长的链表从首元结点开始，走它们之间长度的差值
        pL = headA;
        pS = headB;
        int len = lengthA - lengthB;
        if(len < 0) {       //保证了pL指向长链表，pS指向短链表，且len为非负数
            pL = headB;
            pS = headA;
            len = -len;
        }
        while(len > 0) {
            pL = pL.next;
            len--;
        }

        //3. 让pS与pL同时走，若遇到结点地址相同且不为空时，即为所求结点
        while(pL != pS) {
            pL = pL.next;
            pS = pS.next;
        }
        if(pL == pS && pL != null) {
            return pL;
        }
        return null;
    }


    //力扣：141. 环形链表
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) return true;
        }
        return false;
    }


    //力扣：142. 环形链表 II
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;

        ListNode fast = head;
        ListNode slow = head;
        //1.判断链表是否成环，如果成环，找到fast与slow相遇时的结点
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;
        }
        if(fast == null || fast.next == null) return null;

        //2.将fast移到链表的头部，fast与slow以同样的速度进行遍历，直到它们相遇
        fast = head;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }


    //牛客网：BM16 删除有序链表中重复的元素-II
    public ListNode deleteDuplicates (ListNode head) {
        if(head == null) return null;

        ListNode newHead = new ListNode(-1);
        ListNode lastNode = newHead;
        ListNode cur = head;
        while(cur != null) {
            if(cur.next == null || cur.val != cur.next.val) {
                lastNode.next = cur;
                lastNode = cur;
                cur = cur.next;
            }else {
                while(cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                cur = cur.next;
            }
        }
        lastNode.next = null;
        return newHead.next;
    }
}
